#include<stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_type;
//声明一个双向链表的结构体类型
typedef struct linkNode
{
	data_type data;//数据域//
	struct linkNode* prior;//指向前驱结点
	struct linkNode* next;//指向后继结点
}linkNode,*pLinklist;
//--------------------------函数声明--------------------------
//创建一个空链表
pLinklist list_Create();
//获得指定位置的结点
pLinklist list_get(pLinklist H, int pos);//通过pos 获得第pos个位置的结点
//判断是否尾空链表
int empty(pLinklist H);
//遍历  双向链表
int list_show(pLinklist H);
//头插
int list_head_insert(pLinklist H, data_type value);
//尾插
int list_tail_insert(pLinklist H, data_type value);
//指定位置插入
int list_insert(pLinklist H, data_type value, int pos);//将value插入到第pos结点之前
//销毁链表
int list_free(pLinklist *H);
//删除某一个位置上的结点
int list_delete(pLinklist H, int pos);
//删除value值所在的结点
int list_delete_value(pLinklist H,data_type value);
//修改结点数据  找到原数据  修改为新数据
int list_change_vlaue(pLinklist H,data_type oldvalue,data_type newvalue);
// 向前遍历链表
int list_show_forward(pLinklist H);
// 向后遍历链表
int list_show_back(pLinklist H);

int main(int argc, char const *argv[])
{

    printf("sizeof node :%lu   sizeof pointer:%lu\n",sizeof(linkNode),sizeof(pLinklist));
    //双链表测试
    printf("-------------------\n双链表测试\n----------------------------------\n");
    pLinklist head=list_Create();//创建一个空表
    //尾插
    printf("尾插测试\n");
    list_tail_insert(head,1);
    list_tail_insert(head,2);
    list_tail_insert(head,3);
    list_tail_insert(head,4);
     list_show_back(head);
    // //头插
    list_head_insert(head,7);
    list_head_insert(head,8);
    list_head_insert(head,9);
    list_show_back(head);
    //删除某个值所在的结点
    list_delete_value(head,8);
    list_show_back(head);
    //找某个结点
    pLinklist t=list_get(head,6);
    printf("第6个结点的数据为：%d\n",t->data);
    //在指定位置插入数据
    printf("制定法位置插入数据\n");
    list_insert(head,100,7);
    list_show_back(head);

    printf("前向遍历：\n");
    list_show_forward(head);
    printf("找到100修改为200：\n");
    list_change_vlaue(head,100,200);
    list_show_back(head);
    list_show_forward(head);

    //销毁
    list_free(&head);
    list_show_back(head);
    /* code */
    return 0;
}


//创建一个空链表
pLinklist list_Create()
{
    pLinklist head=(pLinklist)malloc(sizeof(linkNode));
    if(head==NULL)
    {
        printf("malloc faild\n");
        return NULL;
    }
    //头结点  带头结点的双向链表 
    head->prior=head->next=NULL;
    head->data=0;
    return head;

}

pLinklist list_get(pLinklist H, int pos)
{
    if(H==NULL)
    {
        printf("list is error\n");
        return NULL;
    }
    
    if(pos<1&&pos!=0)
    {
        printf("pos is error\n");
        return NULL;
    }
    if(pos==0)
    {
        return H;
    }

    //pos从1开始  头结点不存放数据的
    int i=1;
    pLinklist phead=H->next;
    while(i<pos)
    {
        phead=phead->next;
       if(phead==NULL)
       {
        break;
       }
        i++;
    }
    if(i<pos)//如果上面这个循环结束了 i是比pos小的 
    {
        printf("pos is error2\n");
        return NULL;
    }
    return phead;
}

//判断是否尾空链表  是空 返回1  表不存在:-1  否则返回0
int empty(pLinklist H)
{
    //判表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
     //判空
     if (H->next==NULL)
     {
        printf("list is empty\n");
        return 1;
     }
     return 0;
   
}

int list_head_insert(pLinklist H, data_type value)
{
    if(H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    pLinklist newnode = (pLinklist)malloc(sizeof(linkNode));
    if (newnode == NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    
    newnode->data = value;
    newnode->next = newnode->prior = NULL;

    newnode->data = value;
    newnode->next = newnode->prior = NULL;

    newnode->next = H->next;
    H->next->prior = newnode;
    newnode->prior = H;
    H->next = newnode;
    return 0;
}

int list_tail_insert(pLinklist H, data_type value)
{
    //判表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    pLinklist phead = H;
    while (phead->next != NULL)
    {
        phead =phead->next;
    }

    pLinklist newnode = (pLinklist)malloc(sizeof(linkNode));
    if(newnode == NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    //先将数据更新
    newnode->data=value;
    newnode->next=newnode->prior=NULL;
    //修改指针指向
    phead->next=newnode;
    newnode->prior=phead;
    return 0;
    
}

//指定位置插入
int list_insert(pLinklist H, data_type value, int pos)
{
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if(pos<1)
    {
        printf("pos is error\n");
        return -1;
    }
    pLinklist t=list_get(H,pos-1);//要插入数据的前一个结点
    if (t==NULL)
    {
        printf("insert pos is error\n");
        return -1;
    }
    printf("t->data:%d\n",t->data);
    //插入数据
     //创建一个结点
     pLinklist newnode=(pLinklist)malloc(sizeof(linkNode));
     if(newnode==NULL)
     {
         printf("newnode malloc faild\n");
         return -1;
     }
     //先将数据更新
     newnode->data=value;
     newnode->next=newnode->prior=NULL;
     //修改指针指向
     newnode->next=t->next;//先保存后面的结点
     if(t->next!=NULL)
     {
         t->next->prior=newnode;
     }
     t->next=newnode;
     newnode->prior=t;

     return 0;
    

    
}

//销毁链表
int list_free(pLinklist *H)
{
    if((*H)==NULL)
    {
        printf("list is error\n");
        return -1; 
    }
    pLinklist phead=(*H);//
    while (*H)
    {
       *H=(*H)->next;
       //释放*H
       printf("dfre data:%d\n",phead->data);
        memset(phead,0,sizeof(linkNode));

        free(phead);
        phead=*H;
    }
    //释放*H
    return 0;
    
}

//删除value值所在的结点
int list_delete_value(pLinklist H,data_type value)
{
    //判表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    //判空
    if (H->next==NULL)
    {
       printf("list is empty\n");
       return -1;
    }
    //找值
    pLinklist phead=H->next;
    while (phead!=NULL)
    {
        if(value==phead->data)
        {
            break;
        }
        phead=phead->next;
    }
    if (phead==NULL)//没有找到
    {
        printf("value is not find\n");
       return -1;
    }
    phead->prior->next=phead->next;
    if(phead->next!=NULL)
   { 
    phead->next->prior=phead->prior;
   }

   free(phead);
   return 0;
}
//修改结点数据  找到原数据  修改为新数据
int list_change_vlaue(pLinklist H,data_type oldvalue,data_type newvalue)
{
    //判表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    //判空
    if (H->next==NULL)
    {
       printf("list is empty\n");
       return -1;
    }
    //找值
    pLinklist phead=H->next;
    while (phead!=NULL)
    {
        if(oldvalue==phead->data)
        {
            break;
        }
        phead=phead->next;
    }
    if (phead==NULL)//没有找到
    {
        printf("value is not find\n");
       return -1;
    }
    phead->data = newvalue;
    
}
// 向前遍历链表
int list_show_forward(pLinklist H)
{
    //判表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    //判空
    if (H->next==NULL)
    {
       printf("list is empty\n");
       return -1;
    }

    pLinklist phead=H->next;
    while (phead->next!=NULL)
    {
        phead=phead->next;
    }
    printf("向前遍历双向链表：\n");

    while (phead!=H)
    {
       printf("%d \t",phead->data);
       phead=phead->prior;
    }
    printf("\n");
    return 0;
}
// 向后遍历链表
int list_show_back(pLinklist H)
{
    //判表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    //判空
    if (H->next==NULL)
    {
       printf("list is empty\n");
       return -1;
    }
    //遍历打印
    printf("向后遍历双向链表：\n");
    pLinklist phead=H->next;
    while (phead!=NULL)
    {
       printf("%d \t",phead->data);
       phead=phead->next;
    }
    printf("\n");
    return 0;
    
    
}